CF767C Garland

发布于 2020-10-14 | 分类于树形dp | 2分钟 | 321字数 | 浏览量：

首先可以确定的是，如果点权和不为3的倍数，一定不存在合法方案。

记所有点权和为 $sum$ 。

容易想到，令 $dp[u]$ 表示以 $u$ 为根的子树的点权和，则有转移：

dp[u]=a[u]+\sum_{v \in son_u}dp[v]

然后对于点 $u$ , 有一个儿子 $v$ 使得 $dp[v]=\frac{sum}{3}$ ,那么我们可以将 $v$ 切开，然后 $dp[u]=dp[u]-dp[v]$ 。

最后看是否有两个切点即可。

#include <cstdio>
#include <vector>
#include <iostream>
using namespace std;

const int MAXN = 1000000;
int n , root , sum , a[ MAXN + 5 ] , dp[ MAXN + 5 ];
int v1 , v2;
vector< int > Graph[ MAXN + 5 ]; 

void dfs( int u , int fa ) {
	dp[ u ] = a[ u ];
	for( int i = 0 ; i < Graph[ u ].size( ) ; i ++ ) {
		int v = Graph[ u ][ i ];
		if( v == fa ) continue;
		dfs( v , u ); dp[ u ] += dp[ v ]; 
		
		if( dp[ v ] == sum / 3 ) {
			if( !v1 ) v1 = v;
			else if( !v2 ) v2 = v;
			dp[ u ] -= dp[ v ];
		} 
	} 
}

int main( ) {
	scanf("%d",&n);
	for( int i = 1 , v ; i <= n ; i ++ ) {
		scanf("%d %d",&v,&a[ i ]); sum += a[ i ];
		if( !v ) root = i;
		else {
			Graph[ i ].push_back( v );
			Graph[ v ].push_back( i );
		}
	}
	if( sum % 3 ) {
		printf("-1");
		return 0;
	}
	
	dfs( root , 0 );
	if( !v1 || !v2 ) 
		printf("-1");
	else 
		printf("%d %d\n",v1,v2);
	return 0;
}

CF767C Garland

感谢您的支持，我会继续努力的!